package demo1;

import java.util.HashMap;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //二分查找
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        while (left <= right) {
            int middle = (left+right)/2;
            if (nums[middle] > target) {
                right = middle-1;
            } else if (nums[middle] < target) {
                left = middle+1;
            }else {
                return middle;
            }
        }
        return -1;
    }

    //最小覆盖字串
    public String minWindow(String s, String t) {
        HashMap<Character,Integer> map1 = new HashMap<>();
        HashMap<Character,Integer> map2 = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            char ch = t.charAt(i);
            map1.put(ch,map1.getOrDefault(ch,0)+1);
        }
        int sz = map1.size();int n = s.length();String ret = "";Integer count = 0;
        int min = Integer.MAX_VALUE,begin = -1;
        for (int left=0,right=0;right<n;right++){
            char in = s.charAt(right);
            map2.put(in,map2.getOrDefault(in,0)+1);
            if(map2.get(in).equals(map1.getOrDefault(in,0))){
                count++;
            }
            //right++;
            while(count.equals(sz)) {
                if (right-left+1<min) {
                    begin = left;
                    min = right-left+1;
                }
                char out = s.charAt(left);
                if(map2.get(out).equals(map1.getOrDefault(out,0))){
                    count--;
                }
                map2.put(out,map2.get(out)-1);
                left++;
            }
        }
        if(begin==-1){
            return ret;
        }else{
            return s.substring(begin,begin+min);
        }
    }


    public String minWindow1(String s, String t) {
        HashMap<Character,Integer> map1 = new HashMap<>();
        HashMap<Character,Integer> map2 = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            char ch = t.charAt(i);
            map1.put(ch,map1.getOrDefault(ch,0)+1);
        }
        int n = s.length(); int count = 0; int len = Integer.MAX_VALUE;int m = t.length();
        String ret = "";
        for(int left = 0,right=0;right<n;){
            char in = s.charAt(right);
            if(count!=m) {
                if (map2.getOrDefault(in, 0) < map1.getOrDefault(in, 0)) {
                    count++;
                    map2.put(in, map2.getOrDefault(in, 0) + 1);
                }
                right++;
            } else {
                char out = s.charAt(left);
                if(len>(right-left+1)) {
                    ret = s.substring(left, right);
                }
                if(map1.containsKey(out)) {
                    if (map2.getOrDefault(out, 0) <= map1.getOrDefault(out, 0)) {
                        count--;
                        map2.put(out, map2.get(out) - 1);
                    }
                }
                left++;
            }
        }
        return ret;
    }
}
